package offer;

/**
 * @author Elephas
 * @since 2022/6/18
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap obj = new MyHashMap();
 * obj.put(key,value);
 * int param_2 = obj.get(key);
 * obj.remove(key);
 */

class MyHashMap {
    class Node{
        int key;
        int value;
        Node next;
        public Node(int key, int val, Node next){
            this.key = key;
            this.value = val;
            this.next = next;
        }
        public int getHashCode(){
            return key;
        }
    }
    static final double LOAD_FACTOR = 0.75;
    static final double INCREASE_FACTOR = 1.5;
    private int threshold;
    private Node[] table;
    private final static int DEFAULT_MAX_SIZE = 8;
    private int size;
    private int maxSize;
    public MyHashMap() {
        maxSize = DEFAULT_MAX_SIZE;
        threshold = (int) (DEFAULT_MAX_SIZE * LOAD_FACTOR);
        size = 0;
        table = new Node[maxSize];
    }

    public void put(int key, int value) {
        Node[] tab = table;
        int n = maxSize;
        int i = (n - 1) & hash(key);
        Node p = tab[i];
        boolean replace = false;
        if(p == null){
            tab[i] = new Node(key, value, null);
        }else{
            while(p.next != null){
                if(p.key == key){
                    p.value = value;
                    replace = true;
                    break;
                }
                p = p.next;
            }
            if(p.key == key){
                p.value = value;
                replace = true;
            }else{
                p.next = new Node(key, value, null);
            }
        }
        if(!replace){
            size++;
            if(size > threshold){
                resize();
            }
        }

    }
    static int hash(int key){
        return key;
    }
    public void resize(){
        maxSize = (int) (maxSize * INCREASE_FACTOR);
        threshold = (int) (maxSize * LOAD_FACTOR);
        Node[] newTable = new Node[maxSize];
        int n = maxSize, i;
        for(Node p : table){
            while(p != null){
                Node t = p;
                p = p.next;

                t.next = null;
                i = hash(t.key) & (n - 1);
                Node head = newTable[i];
                if(head == null){
                    newTable[i] = t;
                }else{
                    while(head.next != null){
                        head = head.next;
                    }
                    head.next = t;
                }
            }
        }
        table = newTable;
        return ;
    }
    public int get(int key) {
        Node[] tab = table;
        int n = maxSize;
        int i = (n - 1) & hash(key);
        Node p = tab[i];
        while(p != null){
            if(p.key == key){
                return p.value;
            }
            p = p.next;
        }
        return -1;
    }

    public void remove(int key) {
        Node[] tab = table;
        int n = maxSize;
        int i = (n - 1) & hash(key);
        Node p = tab[i];
        boolean delete = false;
        if(p == null){
            return ;
        }
        if(p.key == key){
            tab[i] = p.next;
            delete = true;
        }else{
            //rehash all elements
            while(p.next != null){
                if(p.next.key == key){
                    p.next = p.next.next;
                    delete = true;
                    break;
                }
                p = p.next;
            }
        }
        if(!delete){
            size--;
        }
        return ;
    }
}

